package com.fw.leetcode.binarysearch;

import com.fw.leetcode.LeetCode;

/**
 * 69. Sqrt(x)
 *
 * Given a non-negative integer x, return the square root of x rounded down to the nearest integer.
 * The returned integer should be non-negative as well.
 * You must not use any built-in exponent function or operator.
 *
 * For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
 *
 * Example 1:
 *  Input: x = 4
 *  Output: 2
 *  Explanation: The square root of 4 is 2, so we return 2.
 *
 * Example 2:
 *  Input: x = 8
 *  Output: 2
 *  Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
 *
 * Constraints:
 *  0 <= x <= 2^31 - 1
 */
public final class Num_0069 implements LeetCode {

    private static class Solution {

        public int mySqrt(int x) { // 乘法容易溢出，但比除法快 1ms
            if (x == 0) return 0;
            if (x < 4) return 1;
            int low = 1;
            int high = 46341; // (int)Math.sqrt(Integer.MAX_VALUE)
            int mid = high / 2;
            int maybe = -1; // 可能值：向下取整后的值，满足条件：maybe * maybe <= x
            while (low <= high) { // 注意 +-1 容易陷入死循环，等号边界条件
                int result = mid * mid;
                if (result < 0 || result > x) { // 大于肯定不是，增加相乘溢出小于0的判断
                    high = mid - 1; // -1 丢弃大了的 mid
                } else if (result == x) { // 等于肯定是
                    return mid;
                } else { // 小于可能是
                    maybe = mid;
                    low = mid + 1; // +1 丢弃小了的 mid
                }
                mid = (low + high) / 2;
            }
            return maybe;
        }

        public int mySqrtDivide(int x) { // 除法
            if (x == 0) return 0;
            if (x < 4) return 1;
            int low = 1;
            int high = 46341; // (int)Math.sqrt(Integer.MAX_VALUE)
            int mid = high / 2;
            int maybe = -1;
            while (low <= high) { // 注意 +-1 容易陷入死循环
                int divide = x / mid;
                if (mid > divide) { // 大于肯定不是
                    high = mid - 1; // -1 丢弃大了的 mid
                } else if (mid == divide) { // 等于肯定是
                    return mid;
                } else { // 小于可能是
                    maybe = mid;
                    low = mid + 1; // +1 丢弃小了的 mid
                }
                mid = (low + high) / 2;
            }
            return maybe;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int x = 0;
        while (x != Integer.MAX_VALUE) {
            if ((int)Math.sqrt(x) != solution.mySqrtDivide(x)) {
                System.out.printf("x: %d => %d , should be %d", x, solution.mySqrtDivide(x), (int)Math.sqrt(x));
                break;
            }
            x++;
        }
    }
}
